1. Field of the Invention
The present invention relates to the field of transactional memory utilization in parallel computing and more particularly to nested transactional memory rollback in parallel computing.
2. Description of the Related Art
Transactional memory techniques attempt to simplify parallel programming by allowing a group of load and store instructions to execute in an atomic way. Generally speaking, transactional memory is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. However, unlike the locking techniques used in most modern multithreaded applications, transactional memory can be viewed as optimistic in that a thread completes modifications to shared memory without regard for the activities of other threads, while recording every performed read and write and buffering the speculative changes to memory.
Transactions conflict when two or more transactions access the same block of memory, and at least one of those accesses is a write access. When utilizing transactional memory, instead of placing the onus on the reader or writer of a block of memory to ensure that the execution of a transaction does not conflict with other transactions in progress, the onus is placed on the transactional memory system to verify that other threads have not concurrently made conflicting references to the block of memory. Such a transactional memory system can be realized in software, hardware, or a combination of the two. The operation in which the memory references of a transaction are checked against other concurrent memory references is often referred to as validation. If validation is successful, at the conclusion of a transaction all memory changes are made permanent in an operation often referred to as a commit. Yet, a transaction can abort at any time, causing all of prior changes performed by the transaction to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, the transaction can be aborted and re-executed from the beginning until the transaction succeeds.
It will be recognized by the skilled artisan, then, that the benefit of the optimistic approach of transactional memory is increased concurrency. Specifically, in the optimistic approach known in the art, no thread of execution need to wait to access a block of memory. Further, different threads of execution can safely and simultaneously modify disjoint parts of a data structure that would otherwise be protected under the same lock. Overall, despite the overhead incurred in retrying failed transactions, in many realistic programs conflicts arise rarely enough that transactional memory techniques may provide an immense performance gain over lock-based protocols on large numbers of processors.
While in many instances, rolling back a failed transaction can be a simple operation of little consequence, a large monolithic transaction can provide a more complex challenge. In the face of a large transaction, an abort deep into the execution will require rolling back and re-executing the entire transaction, potentially repeating a substantial amount of work. To address the challenge of a substantial rollback, nested transactions provide a mechanism in which a grouping of transactions can be nested in respect to one another so that rolling back the grouping requires only a rolling back of transactions up to and including a nest level affected by a conflict scenario. Rolling back only part of a linear nest of transactions minimizes the amount of work that must be repeated by re-execution.
To support the rollback of transactions, a transactional memory system must preserve the original contents of memory locations when speculative changes are made, should an abort require that those changes be undone. To support nested transactions, the transactional memory system must additionally record information about the nesting level at which each memory reference is made, and in order to roll back each nest level independently it must preserve the previous contents of memory locations when speculative changes are made at each nesting level. Upon detecting a conflict in association with a block of memory, the nest level associated with the conflicted block of memory can be recalled and each transaction at each level leading up to the associated nest level can be rolled back with corresponding values restored at each nest level. As long as the values written at each nest level are available for the rollback process, each nest level can be rolled back independent of other nest levels, guaranteeing the minimal rollback required by a conflict scenario. Given the requirement to store substantial data in respect to write operations at each nest level for a nested group of transactions, the bookkeeping requirements can be significant. Notably, in a transactional memory system realized in hardware there is considerably complexity in preserving multiple versions of each memory block in the cases where the memory block is modified at multiple transaction nesting levels.
Despite the convenience of substantial hardware support for nested transaction processing, a more simplistic scheme is possible as well. In the simplistic scheme, only the original contents of memory locations are preserved when speculative changes are made, and when speculative changes are made at multiple nesting levels the previous speculative values are not preserved. While in many conflict scenarios, the information stored by the simplistic scheme suffices in the same way as the substantial support, occasions arise where resource intensive processing is required to compute a nest level required for rollback. This occurs when a value has been written to a block of memory at multiple nest levels, and not having saved the last written value at each nest level the nesting levels cannot be rolled back independently from one another. If a nest level where the latest write to a memory block took place is rolled back, then it is necessary to continue rolling back all the way up to and including the first nest level where that block was written to. The simplistic hardware scheme avoids the bookkeeping complexity introduced by saving multiple modified versions of a memory block, one for each nest level where the block is written to, but at the expense of additional rollback in certain conflict scenarios. Notably, in a transactional memory system realized in hardware the simplistic scheme may be attractive in lower cost implementations where the highest levels of performance are not required.